﻿using System;
using System.Collections.Generic;

namespace Bioinformatics.Types
{
    /// <summary>
    /// Represents a phylogeny which maintains a linked list data-structure
    /// </summary>
    public class DynamicPhylogeny
    {
        public DynamicPhylogenyNode Root { get; private set; }

        /// <summary>
        /// Creates a new instance of the DynamicPhylogeny class using a <see cref="GeneticSequence"/> dictionary and a Newick format string.
        /// </summary>
        /// <param name="newickString">The topology representation in Newick format.</param>
        public DynamicPhylogeny(string newickString)
        {
            Root = recurseTopologyString(newickString);
        }

        /// <summary>
        /// Converts the current dynamic phylogeny representation to a static representation.
        /// </summary>
        /// <returns>The static representation of the current phylogeny</returns>
        public PhylogenyNode[] ToStaticPhylogeny()
        {
            //create a list of all nodes in the current phylogeny
            var nodeList = new List<DynamicPhylogenyNode>();

            //perform breadth first search of tree
            var nodeQueue = new Queue<DynamicPhylogenyNode>();

            //place the root in the queue
            nodeQueue.Enqueue(Root);

            //loop until all items in structure have been explored
            while (nodeQueue.Count > 0)
            {
                //dequeue a node
                DynamicPhylogenyNode currentNode = nodeQueue.Dequeue();

                //add each children to the queue
                if (currentNode.LeftChild != DynamicPhylogenyNode.TerminatorNode)
                    nodeQueue.Enqueue(currentNode.LeftChild);

                if (currentNode.RightChild != DynamicPhylogenyNode.TerminatorNode)
                    nodeQueue.Enqueue(currentNode.RightChild);

                //add the current node to the list
                nodeList.Add(currentNode);
            }

            var staticPhylogenyList = new List<PhylogenyNode>();

            //map the structures
            for (int i = 0; i < nodeList.Count; i++)
                staticPhylogenyList.Add(new PhylogenyNode
                                                 {
                                                     Value = nodeList[i].Value,
                                                     LeftChild = nodeList.IndexOf(nodeList[i].LeftChild),
                                                     RightChild = nodeList.IndexOf(nodeList[i].RightChild)
                                                 });

            //map parents
            for (var i = 0; i < nodeList.Count; i++)
            {
                if (staticPhylogenyList[i].LeftChild != -1)
                    staticPhylogenyList[staticPhylogenyList[i].LeftChild].Parent = i;
                if (staticPhylogenyList[i].RightChild != -1)
                    staticPhylogenyList[staticPhylogenyList[i].RightChild].Parent = i;
            }

            //create and return static phylogeny
            return staticPhylogenyList.ToArray();
        }

        private static DynamicPhylogenyNode recurseTopologyString(string markup)
        {
            if (!markup.Contains(","))
                return new DynamicPhylogenyNode
                           {
                               LeftChild = DynamicPhylogenyNode.TerminatorNode,
                               RightChild = DynamicPhylogenyNode.TerminatorNode,
                               BranchLength = Convert.ToSingle(markup.Contains(":")?markup.Split(':')[1]:"0"),
                               Value = (markup.Contains(":")?markup.Split(':')[0]:markup)
                           };
            int open = 0;
            for (int i = 0; i < markup.Length; i++)
                switch (markup[i])
                {
                    case '(':
                        open++;
                        break;
                    case ')':
                        open--;
                        break;
                    case ',':
                        if (open == 1)
                        {
                            return new DynamicPhylogenyNode
                                       {
                                           LeftChild = recurseTopologyString(markup.Substring(1, i-1)),
                                           RightChild =
                                               recurseTopologyString(markup.Substring(i + 1, markup.Length - (i+2))),
                                           BranchLength = 0,
                                           Value = string.Empty
                                       };
                        }
                        break;
                }
            return DynamicPhylogenyNode.TerminatorNode;
        }
    }

    public class DynamicPhylogenyNode
    {
        public static readonly DynamicPhylogenyNode TerminatorNode;

        static DynamicPhylogenyNode()
        {
            TerminatorNode = new DynamicPhylogenyNode { LeftChild = null, RightChild = null, Value = null };
        }

        public DynamicPhylogenyNode LeftChild { get; set; }
        public DynamicPhylogenyNode RightChild { get; set; }
        public float BranchLength { get; set; }
        public string Value { get; set; }
    }
}